def permute_recursive(s: str) -> list[str]:
    """使用递归方法生成字符串的所有排列"""
    if len(s) <= 1:
        return [s]
    
    result = []
    for i, char in enumerate(s):
        # 生成除当前字符外的剩余字符串
        remaining = s[:i] + s[i+1:]
        # 递归生成剩余字符串的排列
        for perm in permute_recursive(remaining):
            result.append(char + perm)
    return result

def permute_iterative(s: str) -> list[str]:
    """使用迭代方法生成字符串的所有排列"""
    from itertools import permutations
    return [''.join(p) for p in permutations(s)]

def permute_lexicographic(s: str) -> list[str]:
    """使用字典序法生成字符串的所有排列"""
    if not s:
        return []
    
    # 先将字符串转换为字符列表并排序
    chars = sorted(list(s))
    result = []
    
    while True:
        # 添加当前排列
        result.append(''.join(chars))
        
        # 找到下一个字典序排列
        i = len(chars) - 2
        while i >= 0 and chars[i] >= chars[i + 1]:
            i -= 1
        
        if i < 0:
            # 已经是最后一个排列
            break
        
        j = len(chars) - 1
        while chars[j] <= chars[i]:
            j -= 1
        
        # 交换i和j位置的字符
        chars[i], chars[j] = chars[j], chars[i]
        
        # 反转i+1到末尾的字符
        chars[i + 1:] = reversed(chars[i + 1:])
    
    return result

def permute_heap(s: str) -> list[str]:
    """使用Heap算法生成字符串的所有排列"""
    if not s:
        return []
    
    chars = list(s)
    result = []
    n = len(chars)
    
    def generate(k, arr):
        if k == 1:
            result.append(''.join(arr))
        else:
            # 生成k-1个排列
            generate(k - 1, arr)
            
            # 根据k的奇偶性选择交换元素
            for i in range(k - 1):
                if k % 2 == 0:
                    arr[i], arr[k - 1] = arr[k - 1], arr[i]
                else:
                    arr[0], arr[k - 1] = arr[k - 1], arr[0]
                generate(k - 1, arr)
    
    generate(n, chars.copy())
    return result

def permute_generator(s: str):
    """使用生成器实现的字典序排列，节省空间"""
    if not s:
        return
    
    chars = sorted(list(s))
    yield ''.join(chars)
    
    while True:
        # 找到下一个字典序排列
        i = len(chars) - 2
        while i >= 0 and chars[i] >= chars[i + 1]:
            i -= 1
        
        if i < 0:
            break
        
        j = len(chars) - 1
        while chars[j] <= chars[i]:
            j -= 1
        
        chars[i], chars[j] = chars[j], chars[i]
        chars[i + 1:] = reversed(chars[i + 1:])
        
        yield ''.join(chars)

def main():
    """演示各种排列算法的基本用法"""
    # 示例用法
    test_string = "abc"
    
    print(f"🎯 字符串排列算法演示")
    print("=" * 50)
    print(f"原始字符串: '{test_string}'")
    
    # 使用递归方法
    recursive_perms = permute_recursive(test_string)
    print(f"\n📚 递归方法生成的排列 ({len(recursive_perms)} 种):")
    for i, perm in enumerate(recursive_perms, 1):
        print(f"  {i}. {perm}")
    
    # 使用迭代方法
    iterative_perms = permute_iterative(test_string)
    print(f"\n⚡ 迭代方法生成的排列 ({len(iterative_perms)} 种):")
    for i, perm in enumerate(iterative_perms, 1):
        print(f"  {i}. {perm}")
    
    # 使用字典序法
    lexicographic_perms = permute_lexicographic(test_string)
    print(f"\n📖 字典序法生成的排列 ({len(lexicographic_perms)} 种):")
    for i, perm in enumerate(lexicographic_perms, 1):
        print(f"  {i}. {perm}")
    
    # 使用Heap算法
    heap_perms = permute_heap(test_string)
    print(f"\n🔧 Heap算法生成的排列 ({len(heap_perms)} 种):")
    for i, perm in enumerate(heap_perms, 1):
        print(f"  {i}. {perm}")
    
    # 使用生成器法
    print(f"\n🔄 生成器法生成的排列:")
    for i, perm in enumerate(permute_generator(test_string), 1):
        print(f"  {i}. {perm}")
    
    # 验证所有方法结果是否一致
    print(f"\n✅ 验证结果:")
    all_consistent = (
        sorted(recursive_perms) == sorted(iterative_perms) == 
        sorted(lexicographic_perms) == sorted(heap_perms) ==
        sorted(list(permute_generator(test_string)))
    )
    print(f"   所有方法结果一致: {all_consistent}")
    
    # 提示运行性能测试
    print(f"\n💡 提示:")
    print(f"   要运行性能测试，请执行: python performance_test.py")

if __name__ == "__main__":
    main()